package 数据结构OJ;

public class 合并俩个有序链表_06 {

    //      Definition for singly-linked list.
    private class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
        }
    }


    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 == null) return l2;
        if (l2 == null) return l1;
        //引入一个新的头结点
        ListNode head = new ListNode(0);
        ListNode str = head;
        while (l1 != null && l2 != null) {
            //当l1的节点值小于l2的节点值时，
            // 把l1节点地址存到str.next中
            if (l1.val <= l2.val) {
                str.next = l1;
                l1 = l1.next;
            }
            //当l2节点值小于l1节点值时，
            //把l2节点地址存到str.next中
            else {
                str.next = l2;
                l2 = l2.next;
            }
            //str后移一个节点，
            //使str指向最新的节点
            str = str.next;
        }
        if (l1 != null) {
            str.next = l1;
        }
        if (l2 != null) {
            str.next = l2;
        }
        //str现在指向最后的节点，所以只有返回head.next，
        //才能确保正确的返回有序链表
        return head.next;
    }
}